Reference document 1 (Stonebraker et al.) generally explains how column-oriented databases differ from more traditional row-oriented databases. In very general terms, in a traditional row-oriented database engine attributes of a record (or tuple) are placed contiguously in storage. Row-oriented database engines provide good performance for writing (inserting and updating data), and they are efficient for On-Line Transaction Processing (“OLTP”). Stonebraker et al. also disclose an example of a column-oriented database engine in which the values for each single column (or attribute) are stored contiguously. A column-oriented storage layout supposedly allows for better compression of data, because typically the variation among the same attribute for all records is smaller than the variation among all the attributes of a single record. In a modern database server the performance bottleneck is often the data transfer speed to and from the permanent storage, and better compression alleviates this bottleneck. As a result, column-oriented database engines are increasingly popular for applications that involve reading large volumes of data. Such applications are frequently called On-Line Analytical Processing (“OLAP”) applications. OLAP database engines are optimized for reading or query processing in applications wherein a query may span a great deal of all the data stored in the database.
One of the problems associated with the above arrangement is related to the fact that when an attribute of a record in the database is to be updated, it may not be possible to update that piece of data in-place in the compressed form. Typically, the entire compressed data block has to be re-compressed. If there is a large volume of updates to process, this re-compression may have a great adverse effect on the update performance in a column-oriented database which utilizes compression.